/**
 * @Author: code.rookie
 * @ClassName: PerfectSquares
 * @PACKAGE_NAME: PACKAGE_NAME
 * @Version: 1
 */
public class PerfectSquares {
    public int numSquares(int n) {
        int[] array = new int[n + 1];
        for(int size = 1; size <= n; size++) {
            int min = Integer.MAX_VALUE;
            for(int perfect = 1; perfect * perfect <= size; perfect++) {
                min = Math.min(min, array[size - perfect * perfect]);
            }
            array[size] = min + 1;
        }
        return array[n];
    }

}
